public class code1 {
    // 牛客 top101 字符串排列

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        // 这道题目的解决方法和之前的重复数字全排列是相同的

        // 这里是需要先针对子串进行排序操作的
        char[] arr = str.toCharArray();
        Arrays.sort(arr);

        // 将重组后的字符串在赋值回来
        str = new String(arr);


        // 需要创建出一个 boolean 类型的数组，按照 arr 每个元素的位置设置是否已经被使用过
        boolean[] flag = new boolean[str.length()];
        // 之后需要全部设定为 false
        for (int i = 0; i < flag.length; i++) {
            flag[i] = false;
        }

        // 创建一个 String 空子串用来拼接当前的字符串
        String child = "";

        // 在来创建一个 ArrayList 类型的数组，用于存放存在的子串序列
        ArrayList<String> list = new ArrayList<>();

        // 在这里实现一个方法，来实现对于所有子串的获取
        // 在这里就要将之前创建的元素全部传递到 get 方法中
        get(str, flag, child, list);

        return list;
    }

    // 实现 获取子串 方法
    // 这里的元素分别对应，总字符串 str，判定数组 flag，子串 child，返回列表 list
    private void get(String str, boolean[] flag, String child,
                     ArrayList<String> list) {
        // 首先第一步先来设定一下返回条件
        // 这里的返回值条件就是当两个子串当度相同时，表明出现了一种子串序列
        if (str.length() == child.length()) {
            list.add(child);
            return;
        }

        // 这里实现核心的子串拼接方法
        // 要针对每一个元素都进行判断
        for (int j = 0; j < str.length(); j++) {
            // 上来先进行一次针对该子串是否被使用的判断
            // 如果已经被使用就需要跳过本次循环
            // if (flag[j] == true) {
            //     continue;
            // }

            // 之后还要针对相邻的两个相同子串的使用情况进行判断，如果 当前 i-1 位置的子串和 i 位置的子串相同且被使用
            // 此时针对 i 位置元素获取就会出现一种子串重复的情况
            // 同样的需要跳过本次循环
            if (flag[j] || j > 0 && (str.charAt(j) == str.charAt(j - 1)) && !flag[j - 1]) {
                continue;
            }

            // 接下来就要正式使用每一位置上的字符串
            // 第一步就是先设定上已使用标签
            flag[j] = true;
            // 将 j 位置的一个元素进行拼接
            child += str.charAt(j);
            // 进行递归操作
            get(str, flag, child, list);

            // 在进行一次操作后，为了防止遗漏还需要进行 回溯 操作
            // 也就是将当前的 flag 设定为 false
            child = child.replaceAll(".$", "");
            flag[j] = false;
        }
    }
}
